open Graph

module ISP (G: Sig.I) = struct

module B = Builder.I(G)
module N = Oper.Neighbourhood(G)
module S = N.Vertex_Set
open S

let rec cliques gr = 
    let rec expand subg cand currentClique leader= 
        if is_empty subg
		(*currentClique is the largest clique*) 
        then (if (List.length currentClique) > (List.length leader) then currentClique else leader) 
        else (*N(u),where u = a vertex u in SUBG which maximizes | CAND  ^ N(u) |*)
            let nU = fold (fun v tempMax -> (fun l1 l2 ->if (cardinal l1 > cardinal l2) then l1 else l2) 
		                                        tempMax (inter cand (N.set_from_vertex gr v))) subg empty 			
            in					   
            examineCand (diff cand nU) subg cand currentClique leader 
    (*depth-first search in all vertices of CAND,  diff = CAND \ N(u) *)	   
    and examineCand diff subg cand currClique leader = 
        match elements diff with
        | []     -> leader
        | hd::tl -> let nieghborHd = N.set_from_vertex gr hd in
				    let newCand = remove hd cand in
				    (*find the largest independent set in new subtree*)
				    let subtreeLeader = 
					    expand (inter subg nieghborHd) (inter cand nieghborHd) (hd::currClique) leader in 
				    (*vertices for further "exam"*)
				    let rests = remove hd diff in
				    (*Examine other candidates with new leader*)
                    examineCand rests subg newCand currClique subtreeLeader
    in			 
    let v = G.fold_vertex (fun ver vertexSet -> (add ver vertexSet)) gr empty in (*all vertices*) 
    expand v v [] []				

(*transform into complementary graph without loops and multiple edges*)
let conversion gr = 
    let complement gr =
	    (G.fold_vertex (fun v g' ->
	        G.fold_vertex (fun w g' ->
	            if G.mem_edge gr v w then g'
	            else B.add_edge g' v w)
	                gr g')
        gr (B.empty ())) 
	in
    let g' = complement gr in
	(*delete loops*)
    (G.iter_vertex (fun v -> if G.mem_edge gr v v then G.remove_edge g' v v) g');
	(*delete multiple edges*)
    (G.iter_vertex (fun v ->
	      G.iter_vertex (fun w -> if (G.mem_edge gr v w) && (G.mem_edge gr v w) then G.remove_edge g' v w) 
		     g')
       g');
	g'	

end